package com.graph;

import java.util.*;

public class Solution802 {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        List<Integer> res = new ArrayList<>();
        int[] rudu = new int[graph.length];
        LinkedList<Integer> queue = new LinkedList<>();
        List<List<Integer>> listGraph = new ArrayList<>();
        for (int i = 0; i < graph.length; i++) {
            listGraph.add(new ArrayList<>());
        }
        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph[i].length; j++) {
                listGraph.get(graph[i][j]).add(i);
            }
            rudu[i] = graph[i].length;
            if (graph[i].length == 0) queue.add(i);
        }
        while (!queue.isEmpty()) {
            int cur = queue.removeFirst();
            res.add(cur);
            for (Integer i : listGraph.get(cur)) {
                rudu[i]--;
                if (rudu[i] == 0) queue.add(i);
            }
        }
        Collections.sort(res);
        return res;
    }
}
